// https://www.lintcode.com/problem/number-of-a/

public class Solution {
    /**
     * @param s: the given string
     * @return: the number of A
     */
    public int countA(String s) {
        // Write your code here
        return _countA(s, 0, s.length() - 1);
    }

    protected int _countA(String s, int start, int end) {
      if (start <= end) {
        int mid = (start + end) / 2;
        char c = s.charAt(mid);
        if (c == 'B') {
          return _countA(s, mid + 1, end);
        } else {
          int ret = _countA(s, start, mid - 1);
          if (c == 'A') {
            ret += 1 + _countA(s, mid + 1, end);
          }
          return ret;
        }
      }
      return 0;
    }
}